/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * <p>
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 100
 * -10⁴ <= matrix[i][j], target <= 10⁴
 * <p>
 * <p>
 * Related Topics 数组 二分查找 矩阵 👍 733 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

public class ID00074SearchA2dMatrix {
    public static void main(String[] args) {


        Solution solution = new ID00074SearchA2dMatrix().new Solution();


//    System.out.println(solution.searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}}, 3));
        System.out.println(solution.searchMatrix(new int[][]{{1, 3, 5}}, 2));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {

            int m = matrix.length;
            int n = matrix[0].length;
            //find row
            int row = -1;
            int up = 0;
            int down = m - 1;
            while (up <= down) {
                int mid = up + (down - up) / 2;

                if (matrix[mid][0] == target || matrix[mid][n - 1] == target) {
                    return true;
                }

                if (matrix[mid][0] < target && matrix[mid][n - 1] > target) { //in this line
                    row = mid;
                    break;
                } else if (matrix[mid][0] > target) {
                    down = mid - 1;
                } else if (matrix[mid][n - 1] < target) {
                    up = mid + 1;
                }
            }

            if (row < 0) return false;

            int left = 0;
            int right = n - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (matrix[row][mid] == target) {
                    return true;
                } else if (matrix[row][mid] < target) {
                    left = mid + 1;
                } else if (matrix[row][mid] > target) {
                    right = mid - 1;
                }
            }


            return false;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}